package com.love.labuladong.twopoint.slidewindow;

/**
 * @Author : zh
 * @Description : 76 最小覆盖子串
 * @Date : 2024-09-02 11:12
 */
public class MinCoverSubStr {


    public static String minWindow(String s, String t) {
        if(s.length() < t.length()){
            return "";
        }
        char[] sa = s.toCharArray();
        char[] ta = t.toCharArray();

        int[] cnts = new int[256];
        for(char cha : ta){
            cnts[cha]--;
        }
        // 最小覆盖子串长度
        int len = Integer.MAX_VALUE;
        // 从哪个位置开头，发现的这个最小覆盖子串
        int start = 0;
        for (int l = 0, r = 0,debt = ta.length; r < sa.length; r++){
            // s[r] 当前字符 -> int
            // cnts[s[r]] : 当前字符欠债情况，负数就是负债，正数就是多给的
            if(cnts[sa[r]] < 0){
                debt--;
            }

            cnts[sa[r]]++;

            if(debt == 0){
                // r 位置结尾，真的有覆盖子串！
                // 看看这个覆盖字串能不能尽量短
                while (cnts[sa[l]] > 0){
                    // l 位置的字符能拿回
                    cnts[sa[l++]]--;
                }
                // 从while里面出来，r位置结尾的最小覆盖子串
                // l ... r
                if( r - l+1 < len){
                    len = r - l + 1;
                    start = l;
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start,start + len);
    }


    public static void main(String[] args) {
        String s = "habdcfabcy";
        String target = "abc";

        System.out.println(minWindow(s,target));
    }

}
